package leetcode.top100;

import java.util.*;

/**
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 * <p>
 * 输入: nums = [1], k = 1
 * 输出: [1]
 * 说明：
 * <p>
 * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * <p>
 * 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 * <p>
 *
 * @since 2019/12/26 0026 下午 10:40
 */
public class Code347_TopKFrequency_频率前K {
    public static void main(String[] args) {
        Code347_TopKFrequency_频率前K p = new Code347_TopKFrequency_频率前K();
        int[] arr = {1, 1, 1, 2, 2, 3};
        p.topKFrequent(arr, 2);
        System.out.println(res);
    }

    private static List<Integer> res = new LinkedList<>();

    public List<Integer> topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) return res;
        process2(nums, k);
        return res;
    }


    //方式3：先用Hash统计，然后创建桶，根据Hash的频率 找到对应的索引，值放key。
    //逆序遍历桶即可。时空都是O(n)
    private void process3(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //频率作为下标，频率最大是 nums.length
        //这里选用Integer是为了是否真的放了数。如果用int，那么默认是0
        //但是可能会出现很多0.所以还要考虑一个标记数组。
//        Integer[] bucket = new Integer[nums.length+1];
//        int []bucket;
//        int [] filled;

        //考虑到每个频率可能对应不止一个数，所以不能用简单的数组。可以用数组链表
        //频率作为下标，频率最大是 nums.length
        List[] bucketList = new List[nums.length + 1];
        for (Integer key : map.keySet()) {
            int index = map.get(key);
            //bucketList[index]是一个链表。
            if (bucketList[index] == null) bucketList[index] = new LinkedList();
            //同等频率的，都加入到一个集合
            bucketList[index].add(key);
        }
        for (int i = bucketList.length - 1; i >= 0; i--) {
            if (bucketList[i] != null) res.addAll(bucketList[i]);
            if (res.size() == k) return;
        }
    }

    //方法2：Map+堆。
    private void process2(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //
        // 遍历map，用最小堆保存频率最大的k个元素
        Queue<Integer> minQueue =
                //这样写，限定了Queue只能存放map中的key。放其他元素会抛空指针。
                //因为排序的时候需要通过map.get(key)比较
                new PriorityQueue<>((o1, o2) -> map.get(o2) - map.get(o1));
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            //前k个直接放入
            if (minQueue.size() < k) {
                //按照key的个数，构建小跟堆
                minQueue.add(entry.getKey());
                //对于后续的元素，如果其个数大于堆顶，则替代堆顶。
            } else if (entry.getValue() > map.get(minQueue.peek())) {
                minQueue.poll();
                minQueue.add(entry.getKey());
            }
        }

        while (!minQueue.isEmpty()) {
            res.add(minQueue.remove());
        }
        Collections.reverse(res);
    }

    //方法1：Hash统计个数，然后基于个数排序
    private void process1(Integer[] nums, int k) {
        final Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //注意泛型，必须是对象才能用比较器。如果nums是int，那么就不能排序
        //这样写是按照map.key进行排序。key对应的value越大，排到越前。
        //O(nlogk)
        Arrays.sort(nums, (o1, o2) -> map.get(o2) - map.get(o1));
        //按照频率排序
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] != nums[i + 1]) {
                res.add(nums[i]);
                if (res.size() >= k) return;
            }
        }
        //考虑倒数第二个和倒数第一个不等
        if (res.size() < k) res.add(nums[nums.length - 1]);
    }


}
